package com.pan.games.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2021/4/7
 */
public class MergeArray {

    public static final int aa = 10;

    public static final List<String> common = new ArrayList<>();

    static{
        List<String> names = new ArrayList<>(16);

    }


    public static void main(String[] args) {
       //int[][] intervals = {{1,3},{2,6},{15,18},{8,10}};
        //int[][] intervals = {{1,4},{4,5}};
        //int[][] intervals = {{1,4},{2,3}};
        int[][] intervals = {{2,3},{4,5},{6,7},{8,9},{1,10}};
        MergeArray m = new MergeArray();
        m.merge(intervals);

    }

    public int[][] merge(int[][] intervals) {

        if(intervals.length==1){
            return intervals;
        }
         List<int[]> intList = new ArrayList<>();
        //对二维数组进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        mergeIntArray(intervals,intList);

        int[][] scopes = new int[intList.size()][2];
        for (int i = 0; i < intList.size(); i++) {
            int[] ints = intList.get(i);
            scopes[i][0]=ints[0];
            scopes[i][1]=ints[1];
            System.out.println(ints[0]+","+ints[1]);
        }

        return scopes;
    }

    private static void mergeIntArray(int[][] intervals,List<int[]> intList) {

        int curLeft =0;
        int curRight =0;
        boolean notMerge=true;
        for (int i = 0; i < intervals.length-1; i++) {
            if(notMerge){
                curLeft = intervals[i][0];
                curRight = intervals[i][1];
            }
            boolean could = couldMerge(intervals[i],intervals[i+1]);
            if(could){
                curRight =  mergeScope(intervals[i],intervals[i+1]);
                intervals[i+1][1]=curRight;
                notMerge=false;
                if(i==intervals.length-2){
                    int[] oneScope = new int[]{curLeft,curRight};
                    intList.add(oneScope);
                }
            }else{
                int[] oneScope = new int[]{curLeft,curRight};
                intList.add(oneScope);
                notMerge=true;
                if(i==intervals.length-2){
                    intList.add(intervals[i+1]);
                }
            }


        }
    }

    /**
     * 判断是否需要进行合并
     * @param pre
     * @param cur
     * @return
     */
    private static boolean couldMerge(int[] pre, int[] cur) {

        boolean could = false;
        int preLeft = pre[0];
        int preRight = pre[1];

        int curLeft = cur[0];

        if(curLeft<=preRight&&curLeft>=preLeft){
            could=true;
        }
        return could;
    }


    /**
     * 区间合并
     * @param pre
     * @param cur
     * @return
     */
    private static int mergeScope(int[] pre, int[] cur) {

        int preRight = pre[1];
        int curRight =cur[1];

        if(curRight<preRight){
            return preRight;
        }

        return curRight;
    }


    /**
     * 官方解答
     * @param intervals
     * @return
     */
    public int[][] mergeOffice(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

}
